package algorithm.math;

import java.util.ArrayList;
import java.util.List;

/**
 * leetcode : https://leetcode.com/problems/count-primes/description/
 * Difficulty : Easy
 *
 * 给一个数，统计小于这个数的素数的个数。
 * 举个栗子：
 * Input : 10
 * Output : 4 (小于10的素数 2,3,5,7)
 *
 * 从找素数的思路中反着来，找到素数以后，其整数倍的数都是非素数。
 * 所以如果是非素数则跳过，否则其就是素数。
 * （如果一个数，在其之前的素数的倍数都没有把其置为非素数，那么其就是素数）
 * 有那么一点动态规划的思想
 *
 * @Author Antony
 * @Since 2018/7/9 14:35
 */
public class CountPrimes {

    public static void main(String[] args) {
        int n = 10;
        System.out.println(countPrimes(n));
    }

    /**
     * (beats 97.75% - 13ms)
     * 思路，从头到后，如果一个数为素数，则其之后的数都是非素数。
     * 那么无需判断是不是素数（因为判断素数很耗时），只需要看这个数是不是【非素数】 就可以了
     * 因为3肯定是素数，可能的素数在奇数中产生，所以 i=3; i+=2;
     */
    public static int countPrimes(int n) {
        if(n<=2){
            return 0;
        }
        boolean[] arr = new boolean[n]; //默认false，false表示为素数
        int count=1;
        for(int i=3; i<n; i+=2){
            if(arr[i]){
                continue;   //如果为true，表示非素数，跳过
            }
            count++;// 否则该数为素数，count增加
            int index = i;
            while((index+=i) < n){
                arr[index] = true;
            }
        }
        return count;
    }

    /**
     * 还是慢，因为有判断素数的过程，其实可以不需要这个判断
     * (beats 6.35% - 275ms)
     * 声明一个数字 0表示未确定，1表示为素数，-1表示非素数
     * 遇到一个数字如果为0，则判断是否是素数，如果是素数，则倍数位索引全是非素数。
     */
    public static int countPrimes_slow2(int n) {
        if(n <= 2){
            return 0;
        }
        int count = 1;
        int[] arr = new int[n];
        for (int i=3; i<n; i+=2){
            if(arr[i] ==0){   //如果未确定
                if(isPrime(i)){
                    arr[i] = 1;
                    count++;
                    for(int j=2; i*j<n; j++){
                        arr[i*j] = -1;
                    }
                }
            }
        }

        return count;
    }


    // -----------------------------------
    // 时间很慢
    // (beats 3.98% - 363ms)
    public static int countPrimes_slow(int n) {
        int count = 0;
        for(int i=0; i<n; i++){
            if(isPrime(i)) count++;
        }
        return count;
    }

    // 判断数字是否为素数
    static boolean isPrime(int num){
        if(num < 2) return false;
        else if(num == 2) return true;
        else if(num%2 == 0) return false;
        double maxFactor = Math.sqrt(num);
        int i = 3;
        while(i <= maxFactor){
            if(num%i ==0) return false;
            i+=2;
        }
        return true;
    }


    // -----------------------
    //  这是找出素数的方法，超时
    public static int countPrimes_timeOut(int n) {
        if(n <= 2){
            return 0;
        }
        List<Integer> list = new ArrayList<>(n/2);
        list.add(2);
        int num = 3;
        boolean isPrime;
        while(num < n){
            isPrime = true;
            for(int p : list){
                if (num % p == 0){
                    isPrime = false;
                    break;
                }
            }
            if (isPrime){
                list.add(num);
            }
            num+=2;
        }
        return list.size();
    }
}
